COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	    Building Program Models Incrementally from Informal Descriptions
C00007 ENDMK
C⊗;
    Building Program Models Incrementally from Informal Descriptions

			    Brian P. McCune

Abstract.  This thesis presents a solution to one aspect of the program
acquisition problem:  the incremental building of program models from
informal descriptions.  The work includes the definition of a framework
for program acquisition, the explication of a body of knowledge about
program acquisition, and a computer implementation to validate the
approach taken.

The thesis describes a system called the //Program Model Builder/ (PMB),
which builds a complete and consistent program model from small chunks of
program.  These chunks, or //program fragments/, are expressed in an
informal language that is essentially a superset of the language in which
program models are built.  This //program modelling language/ is a very
high level (VHL) programming language which includes some novel constructs
and features important for automatic building, analysis, and modification
of programs.

PMB's knowledge is of the domain of simple symbolic computations, but PMB
is designed to be independent of specific programming domains and
particular program specification techniques.  However, a user is assumed
to be familiar with programming.  PMB has been tested both as a module of
the PSI program synthesis system [Green-76, Green et al.-79] and
independently.  When provided with a frontend parser for the surface form
of the fragment language, PMB would also be a useful programming aid.

PMB deals with program fragments interactively and incrementally because
the user has control of the specification process.  Interesting problems
arise because these fragments may arrive in arbitrary order and may be
ambiguous, incomplete, inconsistent, and nonspecific.  To allow the
current point of focus to change, a fragment includes a pattern expressed
in a //program reference language/ which specifies what part of the model
a fragment refers to.  The system also provides for limited forms of
program modification and canonicalization by the use of equivalence
transformations.

PMB uses a problem solving paradigm that allows subgoals to be dealt with
in an order defined by the user, rather than the system.  Knowledge is
represented as a set of data-driven antecedent rules (demons) that are
triggered by either the input of new fragments or changes in the partial
program model.

In addition to its relevance to artificial intelligence, this thesis may
be of interest in such software systems research areas as semiautomatic
programming aids, intelligent program editors, informal programming
languages, and incremental compilers.

Key Words and Phrases.  Artificial intelligence, knowledge based systems,
automatic programming, program synthesis, program acquisition, program
model building, program completeness, program consistency, program
canonicalization, program modification, program fragments, program
reference language, program modelling language, symbolic computation,
software systems, programming aids, informal programming languages, very
high level languages.